#include<iostream>
#include<ctime>

using namespace std;
const int N=1e5+10;
int a[N];
int n;
int index(int left,int right)
{
	return a[rand()%(right-left+1)+left];//[left,right]区间
}
void Sort(int left,int right)
{
	if(left>=right) return ;
	//1:随机选择基准元素优化
	int p=index(left,right);
	//2：荷兰国旗问题优，三指针划分三块左边小于基准右边大于基准
	int l=left-1,i=left,r=right+1;
	while(i<r)
	{
		if(a[i]<p) swap(a[++l],a[i++]);
		else if(a[i]==p) i++;
		else swap(a[--r],a[i]);
	}
	Sort(left,l);
	Sort(r,right);
}
int main()
{
	srand(time(0));
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	Sort(1,n);
	for(int i=1;i<=n;i++)
	{
		cout<<a[i]<<" ";
	}
	return 0;
}

// p 是随机选择的基准索引（例如 p=3），
// 后续比较用的是 a[p]（即 a[3] 的值）。
// 但问题在于：划分过程中，a[p] 对应的元素可能被 swap 交换到其他位置，
// 导致 a[p] 的值发生变化（不再是最初选择的基准值），
// 后续比较会用错误的值，最终打乱排序逻  辑。
// int index(int left,int right)
// {
// 	return rand()%(right-left+1)+left;//[left,right]区间
// }